A substrate computer network (also referred to herein as a “substrate network” or “underlay network”) includes various digital devices. Each digital device performs one or more functions, such as but not limited to routing data, filtering data, inspecting data, processing data, and/or storing data. A digital device may be a function-specific hardware device or a generic machine configured to perform a particular function. Examples of function-specific hardware devices include a hardware router, a hardware firewall, and a hardware network address translator (NAT). A generic machine, such as a server, may execute various virtual machines and/or software applications performing respective functions. Digital devices within a substrate network are connected by one or more physical links. Examples of physical links include a coaxial cable, an unshielded twisted cable, a copper cable, and an optical fiber.
An overlay computer network (also referred to herein as an “overlay network” or “ON”) is a network abstraction implemented on a substrate network. One or more overlay networks may be implemented on a same substrate network. Hosts in an overlay network are connected by virtual or logical communication paths, each of which corresponds to one or more physical links of the substrate network.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.